package com.hr.剑指offer.work1;

import java.util.Arrays;

/**
 * @author 周恒哲
 * @date 2020/06/16
 * 动态规划
 **/
public class 面试题14_I_剪绳子 {
    public int cuttingRope(int n) {
        //1.创建数组-设置对应的含义,dp[n]为长度为 n 时候，最大的乘积 我们只需求出dp[n]
        int[] dp = new int[n + 1];
        //3.确定初始值
        dp[0] = 0;
        dp[1] = 0;
        dp[2] = 1;
        dp[3] = 2;
        dp[4] = 4;
        dp[5] = 6;
        dp[6] = 9;
        if (n <= 6) {
            return dp[n];
        }
        for (int i = 7; i <= n; i++) {
            dp[i] = dp[i - 3] * 3;
        }
        return dp[n];
    }

    /**
     * 不懂
     *
     * @param n
     * @return
     */
    public int cuttingRope2(int n) {
        if (n >= 1 && n <= 3) {
            return n - 1;
        }
        if (n == 0) {
            return 0;
        }
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        for (int i = 4; i < n; i++) {
            int res = 0;
            for (int j = 1; j < i - 1; j++) {
                res = Math.max(res, dp[j] * (i - j));
            }
            dp[i] = res;
        }
        return dp[n];
    }

    /**
     * 动态规划
     *
     * @param n
     * @return
     */
    public int cuttingRope3(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, 1);
        for (int i = 3; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                dp[i] = Math.max(dp[i], Math.max(j * (i - j), dp[i - j] * j));
            }
        }
        return dp[n];

    }
}
